1. Field of the Invention
The present invention relates to a high-level synthesis apparatus and method for use in the designing of logical circuits in an LSI, the apparatus and method being used for synthesizing circuits whose operations are expressed by operational descriptions (e.g., instructions, functions, procedures); and a recording medium carrying a program for implementing the high-level synthesis method.
2. Description of the Related Art
Conventionally, methods for synthesizing a circuit from operational descriptions which express operations of threads that operate in parallel and which express synchronous data communication between such threads are disclosed, for example, in Japanese Laid-Open Publication No. 10-116302, which has been filed by the Applicant.
The aforementioned conventional method is illustrated in FIG. 1. First, operational descriptions 1 are read, and the order of executing the arithmetic operations included therein is determined by a scheduler 3. Then, a circuit element allocator 5 allocates arithmetic operations and the like to elements (e.g., arithmetic logic units, registers, etc.) in the data path. Then, a control circuit is generated which generates signals controlling the data path such that it executes the arithmetic operations and the like in the order determined by the scheduler 3. Thus, a product circuit 7 is synthesized by this conventional synthesis method.
According to this conventional synthesis method, instructions (e.g., xe2x80x9csendxe2x80x9d, xe2x80x9creceivexe2x80x9d) are provided in an input language for defining a communication procedure (commonly known as a xe2x80x9cprotocolxe2x80x9d) such that data between two threads are transferred in a synchronous manner, i.e., a data transfer between a data-transmitting end and a data-receiving end can begin only after both ends become ready to commence data transfer. Thus, an instruction for sending data (xe2x80x9csendxe2x80x9d) and an instruction for receiving data (xe2x80x9creceivexe2x80x9d) are simply described in the input language. A product circuit is synthesized by additionally generating handshaking circuits for the respective threads for achieving handshaking there between. Thus, the product circuit guarantees synchronous communication between the threads.
However, a circuit which is generated by the aforementioned conventional synthesis method has a problem in that the communication slows down when a series of consecutive communication instructions are executed because such communication instructions are executed in a sequential manner.
For example, consider the two xe2x80x9cSENDxe2x80x9d instructions in a thread 15 included in a set of operational descriptions shown in FIG. 2. In this case, a circuit which is synthesized by the aforementioned conventional synthesis method can execute the communication described as SEND (CH2, D2) only after the communication described as SEND (CH1, D1) occurs. As a result, when handshaking communication is performed in synchronization with a clock signal, the execution of these two xe2x80x9cSEND instructionsxe2x80x9d requires four clock cycles, as shown in FIG. 3.
According to the present invention, there is provided a high-level synthesis apparatus for receiving operational descriptions including synchronous communication instructions between threads which operate in parallel, and for synthesizing a product circuit based on the received operational descriptions, the high-level synthesis apparatus including: an extractor for analyzing the received operational descriptions and extracting consecutive synchronous communication instructions which are of the same kind from among the received operational descriptions; a scheduler for generating scheduling for each thread by bundling together the extracted synchronous communication instructions into one arithmetic operation; and a circuit generator for generating the product circuit based on results of the scheduling, the product circuit being capable of commencing the bundled synchronous communication instructions with the same level of priority based on handshaking.
In one embodiment of the invention the circuit generator includes: a data path element allocation section for, based on the results of the scheduling, selecting and allocating circuit elements which are necessary for constructing a data path; a handshaking circuit addition section for adding a handshaking circuit for each of input/output ports of the data path; a queuing state generation section for adding a queuing state to the results of the scheduling; and a control circuit generation section for generating a control circuit for performing control based on the results of the scheduling with the queuing state added thereto.
In another aspect of the invention, there is provided a high-level synthesis method for receiving operational descriptions including synchronous communication instructions between threads which operate in parallel, and for synthesizing a product circuit based on the received operational descriptions, the method including the steps of: analyzing the received operational descriptions and extracting consecutive synchronous communication instructions which are of the same kind from among the received operational descriptions; generating scheduling for each thread by bundling together the extracted synchronous communication instructions into one arithmetic operation; and generating the product circuit based on results of the scheduling, the product circuit being capable of commencing the bundled synchronous communication instructions with the same level of priority based on handshaking.
In still another aspect of the invention, there is provided a recording medium carrying a program for implementing the aforementioned high-level synthesis method.
Hereinafter, the effects of the present invention will be described.
According to the present invention, operational descriptions including synchronous communications between threads which operate in parallel are analyzed, and any number of consecutive synchronous communications which are of the same kind are extracted. Then, the scheduling for each thread is generated by bundling together the extracted synchronous communications into one arithmetic operation. Based on such scheduling results, the circuit generated by the method of the present invention can commence the bundled synchronous communications with the same level of priority (e.g., at the same time) during a synchronous communication process via handshaking circuits. As a result, the circuit generated by the method of the present invention is capable of operating at a higher speed than conventional circuits in which such synchronous communication instructions are executed in a consecutive manner.
For example, in the set of operational descriptions illustrated in FIG. 2, the two synchronous communications xe2x80x9cSEND (CH1, D1)xe2x80x9d and xe2x80x9cSEND (CH2, D2)xe2x80x9d, which are consecutively described and are of the same kind, have no data dependency on each other. Therefore, it is possible to simultaneously commence the two communications and complete the communications within two clock cycles (see the description of the embodiment of the invention with reference to FIG. 13 for more detailed explanation).
As used herein, two instructions are said to have xe2x80x9cdata dependencyxe2x80x9d on each other if the two instructions can be illustrated as two nodes that are connected to each other by an arrow in a control data flow graph (xe2x80x9cCDFGxe2x80x9d) (e.g., FIG. 5). The control data flow graph of FIG. 5 corresponds to the operational descriptions shown in FIG. 2. For example, the communication instructions xe2x80x9cSEND (CH1, D1)xe2x80x9d and xe2x80x9cSEND (CH2, D2)xe2x80x9d shown in FIG. 2 correspond to the nodes denoted as xe2x80x9cCH1Wxe2x80x9d and xe2x80x9cCH2Wxe2x80x9d of FIG. 5, respectively. Since the nodes CH1W and CH2W are not connected to each other by an arrow, the two communication instructions xe2x80x9cSEND (CH1, D1)xe2x80x9d and xe2x80x9cSEND (CH2, D2)xe2x80x9d do not have any xe2x80x98data dependencyxe2x80x99 on each other.
Even if two synchronous communication instructions interpose a process which is not a synchronous communication instruction described there between, such two synchronous communication instructions can be bundled together as xe2x80x9cconsecutive synchronous communication instructions which are of the same kindxe2x80x9d. However, if two synchronous communication instructions which are of the same kind interpose a different kind of synchronous communication instruction there between (as in a sequence: xe2x80x9cRECEIVE(RECV)xe2x80x9d xe2x80x94xe2x80x9cSENDxe2x80x9d xe2x80x94xe2x80x9cRECEIVE(RECV)xe2x80x9d), the two synchronous communication instructions of the same kind (i.e., RECEIVE(RECV)) cannot be bundled together as xe2x80x9cconsecutive synchronous communication instructions which are of the same kindxe2x80x9d.
The circuit generator selects and allocates circuit elements which are necessary for constructing a data path based on the scheduling results, and adds handshaking circuits to respective input/output ports, thereby mapping arithmetic operations associated with synchronous communication into handshaking circuits. Furthermore, by adding a queuing state to the scheduling results and generating a control circuit accordingly, a control circuit can be provided which is capable of controlling communication operations as dictated by the scheduling results.
A recording medium carrying a program for implementing the high-level synthesis method according to the present invention, when read and executed by a computer, can implement a high-level synthesis apparatus which extracts and bundles together any consecutive synchronous communication instructions that are of the same kind, which generates scheduling for each thread, and which generates a circuit that is capable of commencing the execution of the bundled synchronous communication instructions with the same level of priority.
Thus, the invention described herein makes possible the advantages of (1) providing a high-level synthesis apparatus which is capable of synthesizing a circuit which operates at a higher speed than conventional circuits, based on operational descriptions including synchronous communications, and a method for such high-level synthesis: and (2) providing a recording medium carrying a program for implementing such a high-level synthesis method.
These and other advantages of the present invention will become apparent to those skilled in the art upon reading and understanding the following detailed description with reference to the accompanying figures.